Why use Linked List
As I briefly mentioned in an earlier post on data structures, arrays have some disadvantages such as, not being flexible in terms of extending or reducing its size (because it’s a static data structure) which linked lists address.
What is a Linked List
An linked list is a dynamic linear data structure, where each data element is a separate object with its own memory allocation connected to the other objects via pointers.
These elements (called nodes) comprise of the data and the reference pointing to the next node. The first node is called the head and the last node has a null reference. The number of nodes comprising the list is not fixed and can be changed on demand.
Linked lists come with their own tradeoffs which one should consider. For example, we can’t access a specific element within a linked list without going through all of the nodes. Also, linked lists are bigger in size compared to arrays as we now store next node’s reference pointer (4 bytes extra on 32-bit CPU) with each element.
Linked List applications
Linked lists are very important in software that deals with an unspecified number of data.
A checkout basket of an online store for example. The basket is a list of items a user wants to buy. As we don’t know how many items the user will be buying, we need a dynamic data structure, such as linked lists, for listing all possible items.
Types of Linked Lists
There are two types of linked lists, the singly linked list described above and, the doubly linked list.
In the doubly linked list, the nodes in addition to the singly linked list properties hold a reference of their previous node as well.
Linked List Internals
In order to better understand how linked lists work, we need to take a look at its internals and basic functionalities. So roll your sleeves up and lets jump into some code.
The Node class
Firstly, let us have a look at a general implementation of a node class in a singly linked list, shown below, that we’ll be using for this example.
Iterating a linked list
Iterating a linked list is done by using the next node reference pointer in each node. The next node reference takes us through the linked list node by node, as it is depicted in the diagram below.
Following is the code to iterate the list and print all nodes.
Adding a new node
There are three basic methods on how we can add new nodes to the list. Adding a new node at the top of the linked list replacing the head. Adding a new node to the tail and also, adding a new node in a specific position relative to another node in the list.
Add to the head
We can replace the head of a linked list by creating a new node and assigning the current head as its next node and then, make that new node the head of the list.
Add to the tail
To add a new node at the end/tail of the linked list we need to iterate the list and find the last node. Then we assign the last node’s next reference to the new node we want to add.
Add after another node
We can also add a new node in a specific position in the linked list relatively to another node. We just need to iterate the list find the node we are looking for and add the new node after that. Or add it to the tail if we can’t find it.
Additionally, we can modify the below code to add a node before another node, etc.
Remove a node
To remove a specific node from the list, we need to iterate the nodes and find it. We keep a reference to its previous node. Then, we point the previous’s next reference pointer, to the next node of the one we want to remove.
Extra
After understanding the basics of linked lists, let’s leave our imagination run free and to play a bit more with this data structure.
Let’s have a look at a cool method for checking and removing duplicates in a linked list.
Another cool algorithm is Floyd’s tortoise. This algorithm can check if a singly linked list has a closed cycle.
This can be achieved by iterating a list with two pointers that will move in different speed. In this way, if there is a cycle the two pointers will meet at some point in the future.
How easy it is to implement? Let’s see.
Performance
Now for the cool part let’s see some stats of linked lists about, operation performance with Big-O notation complexities.
Linked list Big-O time complexity is O(n) for Access and Search, whereas, for Insertion and Deletion operations is O(1).
The space complexity of a linked list is O(n).
Again, if you are not familiar with the Big-O notation, I will be writing a post about it as well, so stay tuned.
Linked lists are a powerful data structure that we can use for many important reasons as we discussed in this post, and we also saw how to use them. I hope you now learned what and why linked lists are so important in computer science. I now encourage you to use linked lists in your own projects and where appropriate in order to become more familiar with them.
